package ACWing.SearchAndGraphTheory.BFS;
//845. 八数码

import java.util.*;

/**
 * @author :chenjie
 * @date :Created 2022/12/17 13:01
 */

/**
 * 本题的总体思路：
 * bfs：将所有一步可以走到的节点全部存到队列中，因为队列的先进先出特性所以必定可以保证先遍历完路径为1的节点才能去遍历2的节点所以保证了到某个点的距离最短
 * 而本题难点在于如何存储节点的状态和存储节点对应的距离
 * 存储节点的状态：题目也有提示1 2 3 x 4 6 7 5 8这样输入便是可以将二维数组压成一维。在进行做题
 * 存储节点对应的距离：刚好就对应hashmap类
 */
public class TheEightDigits {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s="";
        for (int i = 0; i < 9; i++) {
            s+=sc.next();
        }
        System.out.println(s);
        System.out.println(bfs(s));
    }
    public static int bfs(String t){
        Queue<String> queue=new ArrayDeque<>();//记录状态
        queue.add(t);
        Map<String ,Integer> map=new HashMap<>();//记录对应的步数
        map.put(t,0);
        int[]dx={1,-1,0,0};
        int[]dy={0,0,1,-1};
        while (!queue.isEmpty()){
            String s = queue.remove();
            if("12345678x".equals(s)){
                return map.get(s);
            }
            int n=s.indexOf('x');
            int x=n/3;
            int y=n%3;
            for (int i = 0; i < 4; i++) {
                int a=x+dx[i],b=y+dy[i];//遍历上下左右
                if(a>=0&&b>=0&&a<3&&b<3){
                    int l=map.get(s);
                    String str=swap(s,n,a*3+b);//必须用对象来接副本不然直接用s=的话会出现意外
                    if(map.containsKey(str)){//如果已经走过来便不在走
                        continue;
                    }
                    map.put(str,l+1);
                    queue.add(str);
                }
            }
        }
        return -1;

    }

    /**
     * setCharAt是精髓所在原本我只能转成char在操作现在可以在字符串上进行修改
     * 交换字符串中的俩个字符
     * @param s 字符串11
     * @param x x的位置下标
     * @param x2 交换位的位置下标
     * @return
     */
    public static String swap(String s,int x,int x2){
        StringBuilder str=new StringBuilder(s);
        str.setCharAt(x,s.charAt(x2));
        str.setCharAt(x2,'x');
        return str.toString();
    }
}
